Password-based security

“Passwords are not broken, we are just using them incorrectly”

Primary tab navigation

Here at IBM Research – Zurich, we recently developed a highly efficient and provably secure cryptographic protocol for protecting user passwords against server compromise. The protocol distributes information required for the password verification process over multiple servers such that attackers have to compromise all involved servers simultaneously to compromise the passwords. In particular, the passwords are stored such that they remain secure even if the corresponding database is stolen. The technology was presented at the 22nd ACM SIGSAC Conference on Computer and Communications Security (CCS) in October 2015.

The problem with passwords

The conventional way to authenticate users by means of a password is to salt and hash the user-provided password attempt and compare it against a corresponding hash value stored in a database. The idea behind storing the user's password not in clear text but rather as a hash value obtained via a one-way hash function (for example, SHA-256) is to prevent adversaries from learning the clear text password in case they manage to steal the password database.

However, the problem is that the hash function can be reversed relatively easily by what are known as offline attacks if the underlying password is chosen by a human. According to the National Institute of Standards and Technology (NIST), a human-generated password with 16 characters has around 30 bits of entropy, which translates to about 1 billion possibilities. Modern password-cracking devices built from commodity hardware can test hundreds of billions of possibilities per second, which means they can crack the hash of the 16-character password in less than one second.

How many characters does your password have?

An attacker obtaining a user's password in clear text is a serious security issue, also because users often reuse the same username and password for different online services. This means that if an attacker succeeds in compromising one service, the other services where the user reused the credentials are also at risk.

Security through collaboration

With our distributed password verification protocol, the password hash is still stored centrally in a service provider's database. However, in order to compute the hash of a user-provided password attempt during login, the service provider needs to be assisted by one or more backend servers. Each backend server holds a secret key that is a crucial input to the hash function. Consequently, a compromised password hash database no longer allows offline attacks because the attacker would also need to compromise all the backend servers to obtain their keys. Clearly, it is much more difficult for an attacker to compromise multiple servers simultaneously rather than a single server, especially if the servers have different operating systems, are hosted in different data centers, and are managed by different system administrators.

Quick recovery from breaches

If a breach of one of the involved servers is detected or suspected, one can perform a clever key refresh, which replaces the server keys with new ones, and the system returns to a secure state without the passwords having been at risk. Such refreshes are so efficient that they can be performed proactively at regular time intervals to limit the time window that an attacker has to compromise all involved servers simultaneously. Another advantage is that the system administrators benefit from being honest about server breaches because they can recover from it via a simple key refresh.

Simpler passwords can become secure

The reason why complicated password rules force users to choose long and complex passwords is that this makes offline attacks on the password hash databases less likely to succeed. But because the hash values created with our protocol are no longer attackable offline, there is no need for complex passwords, provided that the servers throttle failed login attempts or block the accounts after too many failed attempts. This is the same principle that is applied for bank cards: if one enters the wrong PIN code at an ATM too often, the bank card will be blocked.

User-specific document encryption

On top of the security advantage that our protocol provides, it also allows users to derive a user-specific cryptographic key that is dependent on the user's password. A service provider can use this key to encrypt and securely store data and documents that belong to the user, without ever having to store (and thus risk a compromise of) this sensitive key.

Prototype implementation

If you are interested in our protocol, don't hesitate to contact us. We have a highly efficient prototype implementation of our protocol readily available, and it is easy to integrate into existing infrastructures.

Contact the experts